ass Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<bool>> is_symmetry(n, vector<bool>(n, false));


        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (i == j) is_symmetry[i][j] = true;
                else if (j - i == 1 && s[i] == s[j]) is_symmetry[i][j] = true;
                else if (s[i] == s[j] && is_symmetry[i + 1][j - 1] == true) is_symmetry[i][j] = true;
                else is_symmetry[i][j] = false;
            }
        }
        for (auto ele : is_symmetry) {
            for (auto e : ele) {
                cout << e << " ";
            }
            cout << endl;
        }
        cout << endl;

        vector<vector<string>> ans;
        vector<string> sol;
        function<void(int)> dfs = [&](int cur){
            if (cur == s.size()) {
                ans.push_back(sol);
                return;
            }

            for (int i = cur; i < n; i++) {
                if (is_symmetry[cur][i] == true) {
                    sol.push_back(s.substr(cur, i - cur + 1));
                    dfs(i + 1);
                    sol.pop_back();
                }
            }
        };
        dfs(0);
        return ans;
    }
};
